AGC018E Sightseeing Plan <组合数学>

Problem

Sightseeing Plan

Statement

Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the from the west and the from the north as .
Joisino thinks that a touring plan is good if it satisfies the following conditions:
Let be the section where she starts the tour. Then, and hold.
Let be the section where she has lunch. Then, and hold.
Let be the section where she ends the tour. Then, and hold.
By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.
Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo .

Constraints

Input

Input is given from Standard Input in the following format:

Output

Print the number of the different good touring plans, modulo .

Sample

Input #1

1 2	1 1 2 2 3 4 1 1 2 2 3 3

Output #1

Explanation #1
The starting section will always be , and the lunch section will always be . There are four good touring plans where is the ending section, and six good touring plans where is the ending section. Therefore, the answer is .
Input #2

1 2	1 2 3 4 5 6 1 2 3 4 5 6

Output #2

Input #3

1 2	77523 89555 420588 604360 845669 973451 2743 188053 544330 647651 709337 988194

Output #3

137477680

标签：组合数学

Translation

给出三个矩形，，。
求从中任意一点出发，经过中任意指定一点，到达中任意一点，且只能向上走或向右走的路径数。
注意：如果两条路径相同，而在中经过的指定点不同，则视为两条不同路径。即，可将一条路径看成二元组，其中是在中指定经过的点，若两者中任意一者不同，则视为两条不同路径。

Solution

挺麻烦的计数。

设为从走到的方案数，那么有。
引理 1：。
证明：考虑所有从到的路径，其一定经过其仅经过一条形如的边。而经过的路径的条数恰好为，于是有。
引理 2：
证明：

由以上可用类似二维前缀和的方法得到

于是我们有了一个计算从到一个矩形中的任意点的路径个数。类似地，枚举两个矩形各四个基准点即可对于任意在两个矩形中间的点计算从到其再到的路径条数。

对于一条路径，其一定进入一次再从出去一次，设入口和出口曼哈顿距离为，则其一定能对应条中指定点不同的路径。而从左边和下边的每个点进入于从上边和右边的每个点出去的贡献都是可以拆开的，于是枚举入点计算贡献，再枚举出点计算贡献。
具体地，

对于，从进入的路径每条路贡献均为
对于，从进入的路径每条路贡献均为
对于，从出去的路径每条路贡献均为
对于，从出去的路径每条路贡献均为

附上官方题解

Code

#include <bits/stdc++.h>
#define MX 2000000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
lnt fac[MX+5], inv[MX+5];
int X1, X2, X3, X4, X5, X6;
int Y1, Y2, Y3, Y4, Y5, Y6;
void init() {
    fac[0] = inv[0] = inv[1] = 1;
    for (int i = 1; i <= MX; i++) fac[i] = fac[i-1]*i%P;
    for (int i = 2; i <= MX; i++) inv[i] = (P-P/i*inv[P%i]%P)%P;
    for (int i = 2; i <= MX; i++) inv[i] = inv[i]*inv[i-1]%P;
}
lnt F(int n, int m) {return fac[n+m]*inv[n]%P*inv[m]%P;}
lnt calc(int sx, int sy, int tx, int ty) {
    lnt ret = 0;
    for (int x = X3, y = Y3; x <= X4; x++)
        ret = (ret+1LL*(P-x-y)*F(x-sx, y-sy-1)%P*F(tx-x, ty-y)%P)%P;
    for (int x = X3, y = Y3; y <= Y4; y++)
        ret = (ret+1LL*(P-x-y)*F(x-sx-1, y-sy)%P*F(tx-x, ty-y)%P)%P;
    for (int x = X3, y = Y4; x <= X4; x++)
        ret = (ret+1LL*(x+y+1)*F(x-sx, y-sy)%P*F(tx-x, ty-y-1)%P)%P;
    for (int x = X4, y = Y3; y <= Y4; y++)
        ret = (ret+1LL*(x+y+1)*F(x-sx, y-sy)%P*F(tx-x-1, ty-y)%P)%P;
    return ret;
}
int main() {
    init(); lnt ans = 0;
    read(X1), read(X2), read(X3), read(X4), read(X5), read(X6);
    read(Y1), read(Y2), read(Y3), read(Y4), read(Y5), read(Y6);
    ans = (ans+calc(X1-1, Y1-1, X5, Y5))%P;
    ans = (ans+calc(X1-1, Y1-1, X6+1, Y6+1))%P;
    ans = (ans-calc(X1-1, Y1-1, X5, Y6+1)+P)%P;
    ans = (ans-calc(X1-1, Y1-1, X6+1, Y5)+P)%P;
    ans = (ans+calc(X2, Y2, X5, Y5))%P;
    ans = (ans+calc(X2, Y2, X6+1, Y6+1))%P;
    ans = (ans-calc(X2, Y2, X5, Y6+1)+P)%P;
    ans = (ans-calc(X2, Y2, X6+1, Y5)+P)%P;
    ans = (ans-calc(X1-1, Y2, X5, Y5)+P)%P;
    ans = (ans-calc(X1-1, Y2, X6+1, Y6+1)+P)%P;
    ans = (ans+calc(X1-1, Y2, X5, Y6+1))%P;
    ans = (ans+calc(X1-1, Y2, X6+1, Y5))%P;
    ans = (ans-calc(X2, Y1-1, X5, Y5)+P)%P;
    ans = (ans-calc(X2, Y1-1, X6+1, Y6+1)+P)%P;
    ans = (ans+calc(X2, Y1-1, X5, Y6+1))%P;
    ans = (ans+calc(X2, Y1-1, X6+1, Y5))%P;
    return printf("%lld\n", ans), 0;
}